package com.zjj.lbw.algorithm.dp;

/**
 * @author zhanglei.zjj
 * @description leetcode_718. 动态规划
 * 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
 * 输出：3
 * 解释：长度最长的公共子数组是 [3,2,1] 。
 * 示例 2：
 *
 * 输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
 * 输出：5
 *
 *
 * 提示：
 *
 * 1 <= nums1.length, nums2.length <= 1000
 * 0 <= nums1[i], nums2[i] <= 100
 * @date 2023/7/18 15:39
 */
public class MaxRepeatedSubarray_leetode_718 {
    // 一维dp数组解法
    public int findLength(int[] nums1, int[] nums2) {
        int n1Length = nums1.length;
        int n2Length = nums2.length;

        int[] dp = new int[n2Length + 1];
        int result = 0;
        for (int i = 1; i <= n1Length; i++) {
            // 为了防止本轮计算覆盖上一轮数据要采用倒序
            for (int j = n2Length; j >= 1; j--) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                } else {
                    // 如果本轮元素不相同，要开启新一轮计数，因此本轮数据要置为0
                    dp[j] = 0;
                }
                result = Math.max(result, dp[j]);
            }
        }

        return result;
    }

    // 标准dp数组解法
    public int findLength1(int[] nums1, int[] nums2) {
        int n1Length = nums1.length;
        int n2Length = nums2.length;

        // dp数组表示遍历到nums1的下标为i-1, nums2的下标为j-1时，对应的公共子数组的最大长度
        int[][] dp = new int[n1Length + 1][n2Length + 1];
        int result = 0;
        for (int i = 1; i <= n1Length; i++) {
            for (int j = 1; j <= n2Length; j++) {
                // 只有当前元素相等时候才更新本轮dp数组的值，如果不相等本轮dp数组值为默认值0
                // 对应具体场景就是：加入之前出现过公共子数组，后来某个元素不相同，然后中断了，需要重新计数
                if (nums1[i - 1] == nums2[j - 1]) {
                    // 在上一轮的基础上又多了一个公共元素
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    result = Math.max(result, dp[i][j]);
                }
            }
        }

        return result;
    }
}
